2351. Дейкстра

Дан ориентированный взвешенный граф. Найдите кратчайшее расстояние от одной заданной вершины до другой.

Вход. В первой строке содержится три числа n, s и f (1 ≤ n ≤ 2000; 1 ≤ s, f ≤ n), где n – количество вершин графа, s – начальная вершина, а f – конечная. В следующих n строках по n чисел – матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса. На главной диагонали матрицы всегда записаны нули.

Выход. Вывести искомое расстояние или -1, если пути не существует.

Пример входа	Пример выхода
3 1 2 0 -1 2 3 0 -1 -1 4 0	6

РЕШЕНИЕ

графы – алгоритм Дейкстры

Анализ алгоритма

Граф задан весовой матрицей. Для решения задачи необходимо реализовать алгоритм Дейкстры.

Пример

Приведенный в примере граф имеет вид:

Кратчайший путь из 1 в 2 равен 2 + 4 = 6.

Реализация алгоритма

Реализуем алгоритм Дейкстры на весовой матрице. Объявим глобальные константы и массивы.

#define MAX 2001

#define INF 0x3F3F3F3F

int g[MAX][MAX], used[MAX], dist[MAX];

Функция Relax релаксирует ребро (i, j).

void Relax(int i, int j)

{

if (dist[i] + g[i][j] < dist[j])

dist[j] = dist[i] + g[i][j];

}

Основная часть программы. Читаем входные данные.

scanf("%d %d %d",&n,&s,&f);

Инициализация массивов.

memset(g,0x3F,sizeof(g));

memset(used,0,sizeof(used));

memset(dist,0x3F,sizeof(dist));

dist[s] = 0;

Читаем весовую матрицу.

for(i = 1; i <= n; i++)

for(j = 1; j <= n; j++)

scanf("%d",&g[i][j]);

Запускаем алгоритм Дейкстры. Исток находится в вершине s.

for(i = 1; i < n; i++)

{

min = INF; v = -1;

for(j = 1; j <= n; j++)

if (used[j] == 0 && dist[j] < min) {min = dist[j]; v = j;}

Граф может быть несвязным. Если v = -1, то следующая вершина v не найдена.

if (v < 0) break;

Релаксируем ребра, исходящие из вершины v.

for(j = 1; j <= n; j++)

if (used[j] == 0 && g[v][j] != -1) Relax(v,j);

Отмечаем, что кратчайшее расстояние до вершины v из источника s уже вычислено.

used[v] = 1;

}

Выводим ответ.

if (dist[f] == INF) printf("-1\n");

else printf("%d\n",dist[f]);

Java реализация

import java.util.*;

public class Main

{

static final int INFINITY = 2000000000;

static int g[][], used[], dist[];

static void Relax(int i, int j)

{

if (dist[i] + g[i][j] < dist[j])

dist[j] = dist[i] + g[i][j];

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int s = con.nextInt();

int f = con.nextInt();

g = new int[n+1][n+1];

for (int[] row: g) Arrays.fill(row, INFINITY);

used = new int[n+1]; Arrays.fill(used, 0);

dist = new int[n+1]; Arrays.fill(dist, INFINITY);

dist[s] = 0;

for (int i = 1; i <= n; i++)

for (int j = 1; j <= n; j++)

g[i][j] = con.nextInt();

for (int i = 1; i < n; i++)

{

// find vertex w with minimum d[w] among not used vertices

int min = INFINITY, v = -1;

for (int j = 1; j <= n; j++)

if (used[j] == 0 && dist[j] < min) { min = dist[j]; v = j; }

// no more vertices to add

if (v < 0) break;

// relaxate all edges outgoing from v

// process edge v -> j

for (int j = 1; j <= n; j++)

if (used[j] == 0 && g[v][j] != -1) Relax(v, j);

// shortest distance to v is found

used[v] = 1;

}

if (dist[f] == INFINITY) System.out.println(-1);

else System.out.println(dist[f]);

con.close();

}

}